ProgrammingAlgorithm

백준 5525 IOIOI

boj 5525, 백준 5525

백준 5525 IOI는 I와 O로 이루어진 문자열에서 연속적으로 IOI로 이어진 문자 Pn이 몇개 있는지 그 개수를 세는 문제이다. 위 문제에서와 같이 P1은 IOI P2는 IOIOI와 같이 IOI가 연속적으로 붙어 있는 문자로 존재하게 된다. 여기서 N이라는 숫자가 주어지게 되는데 Pn을 만족하는 문자열이 몇군데 존재하는지 찾는 문제이다.

이 문제는 Pn의 특성을 알면 쉽게 풀 수 있다. 만약 길이가 1인 IOI를 Pn에서 찾는다고 하면 Pn의 연속된 IOI에서 길이가 1인 IOI의 개수는 Pn-1(length)+1가 나오게 된다.

예를들어 IOIOIOI에서 길이가 1인 IOI가 몇개인지 세면 IOI는 총 3개가 존재한다. 만약 길이가 2인 IOI를 세면 어떻게 되겠는가? 3-2+1 = 2 즉 2개가 존재한다. 이러한 방식을 통해 우리는 문자열에서 최대로 이어져 있는 Pn들을 찾으면 된다. 그리고 이 Pn들을 바탕으로 길이가 n이상인 IOI의 개수를 찾아낼 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
#include<string.h>
#define INF 987654321

using namespace std;

int n, m;
string s;

int main()
{
	//freopen("input.txt", "r", stdin);

	cin >> n >> m >> s;

	int cnt = 0;
	bool ok = false;

	vector<int> cnts;
	for (int i = 2; i < m; i++)
	{
		if (s[i] == 'I' && s[i - 1] == 'O' && s[i - 2] == 'I')
		{
			if (ok)
				cnt++;
			else
			{
				ok = true;
				cnt = 1;
			}
		}
		else if (ok && s[i] == 'O')
		{

		}
		else
		{
			ok = false;
			if (cnt>=n)
				cnts.push_back(cnt);
			cnt = 0;
		}
	}
	if (cnt>=n)
		cnts.push_back(cnt);

	int sum = 0;
	for (int i = 0; i < cnts.size(); i++)
		sum += cnts[i] - n + 1;

	cout << sum << endl;
		

	return 0;

}
공유하기